1. Field of the Invention
The present invention relates generally to a mobile communication system, and in particular, to an apparatus and method for coding and decoding semi-systematic block Low Density Parity Check (LDPC) codes.
2. Description of the Related Art
In communications, the most essential task is to efficiently and reliably transmit data over a channel. The next generation multimedia mobile communication system, currently under active research, requires a high-speed communication system capable of processing and transmitting different types of information, such as image and radio data, beyond the early voice-oriented service. Therefore, it is essential to increase system efficiency using a channel coding scheme appropriate for the system.
However, transmission data inevitably suffers errors due to noise, interference, and fading according to channel conditions, causing a loss of a great amount of information. In order to reduce the loss of the information, various error control schemes are currently in use and are based in part on channel characteristics to thereby improve the reliability of the mobile communication system. The most basic one of the error control schemes uses error correction codes.
FIG. 1 is a diagram illustrating a transceiver in a conventional mobile communication system. Referring to FIG. 1, a transmitter 100 includes an encoder 111, a modulator 113, and a radio frequency (RF) processor 115, and a receiver 150 includes an RF processor 151, a demodulator 153, and a decoder 155.
In the transmitter 100, transmission information data ‘u’ is generated and delivered to the encoder 111. The encoder 111 generates a coded symbol ‘c’ by coding the information data ‘u’ with a predetermined coding scheme, and outputs the coded symbol ‘c’ to the modulator 113. The modulator 113 generates a modulation symbol ‘s’ by modulating the coded symbol ‘c’ with a predetermined modulation scheme, and outputs the modulation symbol ‘s’ to the RF processor 115. The RF processor 115 RF-processes the modulation symbol ‘s’ output from the modulator 113, and transmits the RF-processed signal via an antenna ANT.
The signal transmitted by the transmitter 100 is received at the receiver 150 via its antenna ANT, and then delivered to the RF processor 151. The RF processor 151 RF-processes the received signal, and outputs the RF-processed signal ‘r’ to the demodulator 153. The demodulator 153 demodulates the RF-processed signal ‘r’ output from the RF processor 151 using a demodulation scheme corresponding to the modulation scheme applied in the modulator 113, and outputs the demodulated signal ‘x’ to the decoder 155. The decoder 155 decodes the demodulated signal ‘x’ output from the demodulator 153 using a decoding scheme corresponding to the coding scheme applied in the encoder 111, and finally outputs the decoded signal ‘û’ as restored information data. In order for the receiver 150 to decode the information data ‘u’ without errors, transmitted by the transmitter 100, there is a need for a high-performance encoder and decoder. Particularly, because a radio channel environment should be taken into consideration because of the characteristics of a mobile communication system, errors that can be generated due to the radio channel environment should be considered more seriously.
As described above, the error control scheme uses error correction codes, and the most typical error correction codes include turbo codes and low-density parity check (LDPC) codes.
It is well known that, during high-speed data transmission, the turbo code is superior in performance gain to a convolutional code that is conventionally used for error correction. The turbo code is advantageous in that it can efficiently correct an error caused by noise generated in a transmission channel, thereby increasing the reliability of the data transmission. The LDPC code can be decoded using an iterative decoding algorithm base on a sum-product algorithm in a factor graph. Because a decoder for the LDPC code uses the sum-product algorithm-based iterative decoding algorithm, it is less complex than a decoder for the turbo code. In addition, the decoder for the LDPC code is easily implemented with a parallel processing decoder, compared with the decoder for the turbo code.
Shannon's channel coding theorem shows that reliable communication is possible only at a data rate not exceeding a channel capacity. However, Shannon's channel coding theorem has proposed no detailed channel coding and decoding method for supporting a data rate up to the maximum channel capacity limit. Generally, although a random code having a very large block size exhibits a performance approximating a channel capacity limit of Shannon's channel coding theorem, when a MAP (Maximum A Posteriori) or ML (Maximum Likelihood) decoding method is used, it is actually impossible to implement the decoding method because of its heavy calculation load.
The turbo code was proposed by Berrou, Glavieux, and Thitimajshima in 1993, and exhibits a superior performance that approximates a channel capacity limit of Shannon's channel coding theorem. The proposal of the turbo code triggered active research on iterative decoding and graphical expression of codes. Further, LDPC codes proposed by Gallager in 1962 have been newly spotlighted in the research.
Cycles exist in a factor graph of the turbo code and the LDPC code, and it is well known that iterative decoding in the factor graph of the LDPC code, where cycles exist, is suboptimal. Also, it has been experimentally proven that the LDPC code has excellent performance through iterative decoding. The LDPC code known to have the highest performance ever, exhibits performances having a difference of only about 0.04 [dB] at a channel capacity limit of Shannon's channel coding theorem at a bit error rate (BER) 10−5, using a block size 107.
In addition, although an LDPC code defined in Galois Field (GF) with q>2, i.e., GF(q), increases in complexity in its decoding process, it is much superior in performance to a binary code. However, there is no satisfactory theoretical description of successful decoding by an iterative decoding algorithm for the LDPC code defined in GF(q).
The LDPC code, proposed by Gallager, is defined by a parity check matrix in which major elements have a value of 0 and minor elements, except the elements having the value of 0, have a non-zero value, e.g., a value of 1. In the following description, it will be assumed that a non-zero value is a value of 1. For example, an (N, j, k) LDPC code is a linear block code having a block size N, and is defined by a sparse parity check matrix in which each column has j elements having a value of 1, each row has k elements having a value of 1, and all of the elements, except for the elements having the value of 1, have a value of 0.
An LDPC code in which a weight of each column in the parity check matrix is fixed to ‘j’ and a weight of each row in the parity check matrix is fixed to ‘k’, is called a “regular LDPC code.” Herein, the “weight” refers to the number of elements having a non-zero value among the elements included in the parity check matrix.
Unlike the regular LDPC code, an LDPC code in which the weight of each column in the parity check matrix and the weight of each row in the parity check matrix are not fixed is called an “irregular LDPC code.” It is generally known that the irregular LDPC code is superior in performance to the regular LDPC code. However, using the irregular LDPC code, because the weight of each column and the weight of each row in the parity check matrix are not fixed, i.e., are irregular, the weight of each column in the parity check matrix and the weight of each row in the parity check matrix must be properly adjusted in order to guarantee the superior performance.
FIG. 2 is a diagram illustrating a parity check matrix of a conventional (8, 2, 4) LDPC code. Referring to FIG. 2, a parity check matrix H of the (8, 2, 4) LDPC code includes 8 columns and 4 rows, wherein a weight of each column is fixed to 2 and a weight of each row is fixed to 4. Because the weight of each column and the weight of each row in the parity check matrix are regular as stated above, the (8, 2, 4) LDPC code illustrated in FIG. 2 is a regular LDPC code.
FIG. 3 is a diagram illustrating a factor graph of the (8, 2, 4) LDPC code illustrated in FIG. 2. Referring to FIG. 3, a factor graph of the (8, 2, 4) LDPC code includes 8 variable nodes of x1 300, x2 302, x3 304, x4 306, x5 308, x6 310, x7 312, and x8 314, and 4 check nodes 316, 318, 320, and 322. When an element having a value of 1, i.e., a non-zero value, exists at a point where an ith row and a jth column of the parity check matrix of the (8, 2, 4) LDPC code cross each other, a branch is created between a variable node xi and a jth check node.
Because the parity check matrix of the LDPC code has a very small weight, it is possible to perform iterative decoding even in a block code having a relatively large size, that exhibits performance approximating a channel capacity limit of Shannon's channel coding theorem, such as a turbo code, while continuously increasing a block size of the block code. MacKay and Neal have proven that an iterative decoding process of an LDPC code using a flow transfer scheme approximates an iterative decoding process of a turbo code in performance.
In order to generate a high-performance LDPC code, the following conditions should be satisfied.
(1) Cycles in a factor graph of an LDPC code should be considered.
The term “cycle” refers to a loop formed by the edges connecting the variable nodes to the check nodes in a factor graph of an LDPC code, and a length of the cycle is defined as the number of edges constituting the loop. A long cycle indicates that the number of edges connecting the variable nodes to the check nodes constituting the loop in the factor graph of the LDPC code is large. In contrast, a short cycle indicates that the number of edges connecting the variable nodes to the check nodes constituting the loop in the factor graph of the LDPC code is small.
As cycles in the factor graph of the LDPC code become longer, the performance efficiency of the LDPC code increases. That is, when long cycles are generated in the factor graph of the LDPC code, it is possible to prevent performance degradation such as an error floor occurring when too many cycles with a short length exist in the factor graph of the LDPC code.
(2) Efficient coding of an LDPC code should be considered.
It is difficult for the LDPC code to undergo real-time coding compared with a convolutional code or a turbo code because of its high coding complexity. In order to reduce the coding complexity of the LDPC code, a Repeat Accumulate (RA) code has been proposed. However, the RA code also has a limitation in reducing the coding complexity of the LDPC code. Therefore, efficient coding of the LDPC code should be taken into consideration.
(3) Degree distribution in a factor graph of an LDPC code should be considered.
Generally, an irregular LDPC code is superior in performance to a regular LDPC code, because a factor graph of the irregular LDPC code has various degrees. The term “degree” refers to the number of edges connected to the variable nodes and the check nodes in the factor graph of the LDPC code. Further, the phrase “degree distribution” in a factor graph of an LDPC code refers to a ratio of the number of nodes having a particular degree to the total number of nodes. It has been proven by Richardson that an LDPC code having a particular degree distribution is superior in performance.
FIG. 4 is a diagram illustrating a parity check matrix of a conventional block LDPC code. Before a description of FIG. 4 is given, it should be noted that the block LDPC code is a new LDPC code for which efficient coding, efficient storage, and performance improvement of a parity check matrix were considered, and the block LDPC code is an LDPC code extended by generalizing a structure of a regular LDPC code.
Referring to FIG. 4, a parity check matrix of the block LDPC code is divided into a plurality of partial blocks, and a permutation matrix is mapped to each of the partial blocks. In FIG. 4, ‘P’ represents a permutation matrix having an Ns×Ns size, and a superscript (or exponent) apq of the permutation matrix P is either 0≦apq≦Ns−1 or apq=∞. In addition, ‘p’ indicates that a corresponding permutation matrix is located in the pth row of the partial blocks of the parity check matrix, and ‘q’ indicates that a corresponding permutation matrix is located in the qth column of the partial blocks of the parity check matrix. That is, Papq represents a permutation matrix located in a partial block, where the pth row and the qth column of the parity check matrix including a plurality of partial blocks cross each other. That is, the ‘p’ and the ‘q’ represent the number of rows and the number of columns of partial blocks mapped to an information part in the parity check matrix, respectively.
FIG. 5 is a diagram illustrating the permutation matrix P of FIG. 4. As illustrated in FIG. 5, the permutation matrix P is a square matrix having an Ns×Ns size, and each of Ns columns included in the permutation matrix P has a weight of 1 and each of Ns rows included in the permutation matrix P also has a weight of 1. Herein, although a size of the permutation matrix P is expressed as Ns×Ns, it will also be expressed as Ns because the permutation matrix P is a square matrix.
In FIG. 4, a permutation matrix P with a superscript apq=0, i.e., a permutation matrix P0, represents an identity matrix INs×Ns, and a permutation matrix P with a superscript apq=∞, i.e., a permutation matrix P∞, represents a zero matrix. Herein, INs×Ns represents an identity matrix with a size Ns×Ns.
In the entire parity check matrix of the block LDPC code illustrated in FIG. 4, because the total number of rows is Ns×p and the total number of columns is Ns×q (for p≦q), when the entire parity check matrix of the LDPC code has a full rank, a coding rate can be expressed as shown in Equation (1), regardless of a size of the partial blocks.
                    R        =                                                                              N                  s                                ×                q                            -                                                N                  s                                ×                p                                                                    N                s                            ×              q                                =                                                    q                -                p                            q                        =                          1              -                              p                q                                                                        (        1        )            
If apq≠∞ for all p and q, the permutation matrices corresponding to the partial blocks are not zero matrices, and the partial blocks constitute a regular LDPC code in which the weight value of each column and the weight value of each row in each of the permutation matrices corresponding to the partial blocks are p and q, respectively. Herein, each of permutation matrices corresponding to the partial blocks will be referred to as a “partial matrix.”
Because (p−1) dependent rows exist in the entire parity check matrix, a coding rate is greater than the coding rate calculated by Equation (1). In the case of the block LDPC code, if a weight position of a first row of each of the partial matrices included in the entire parity check matrix is determined, the weight positions of the remaining (Ns−1) rows can be determined. Therefore, the required size of a memory is reduced to 1/Ns as compared with the case in which the weights are irregularly selected to store information on the entire parity check matrix.
As described above, the term “cycle” refers to a loop formed by the edges connecting the variable nodes to the check nodes in a factor graph of an LDPC code, and a length of the cycle is defined as the number of edges constituting the loop. A long cycle indicates that the number of edges connecting the variable nodes to the check nodes constituting the loop in the factor graph of the LDPC code is large. As cycles in the factor graph of the LDPC code become longer, the performance efficiency of the LDPC code increases. However, as cycles in the factor graph of the LDPC code become shorter, an error correction capability of the LDPC code decreases because performance degradation such as an error floor occurs. That is, when there are many cycles with a short length in a factor graph of the LDPC code, information on a particular node belonging to the cycle with a short length, starting therefrom, returns after a small number of iterations. As the number of iterations increases, the information returns to the corresponding node more frequently, such that the information cannot be correctly updated, thereby deteriorating an error correction capability of the LDPC code.
FIG. 6 is a diagram illustrating a cycle structure of a block LDPC code of which a parity check matrix includes 4 partial matrices. However, before a description of FIG. 6 is given, it should be noted that the block LDPC code is a new LDPC code for which efficient coding, efficient storage, and performance improvement of a parity check matrix were considered. The block LDPC code is also an LDPC code extended by generalizing a structure of a regular LDPC code.
A parity check matrix of the block LDPC code illustrated in FIG. 6 includes 4 partial blocks. Further, a diagonal line represents a position where the elements having a value of 1 are located, and the portions other than the diagonal-lined portions represent positions where the elements having a value of 0 are located. In addition, ‘P’ represents the same permutation matrix as the permutation matrix described in conjunction with FIG. 5.
In order to analyze a cycle structure of the block LDPC code illustrated in FIG. 6, an element having a value of 1 located in an ith row of a partial matrix Pa is defined as a reference element, and an element having a value of 1 located in the ith row will be referred to as a “0-point.” Herein, “partial matrix” will refer to a matrix corresponding to the partial block. The 0-point is located in an (i+a)th column of the partial matrix Pa.
An element having a value of 1 in a partial matrix Pb, located in the same row as the 0-point, will be referred to as a “1-point.” Accordingly, the 1-point is located in an (i+b)th column of the partial matrix Pb.
An element having a value of 1 in a partial matrix Pc, located in the same column as the 1-point, will be referred to as a “2-point.” Because the partial matrix Pc is a matrix acquired by shifting respective columns of an identity matrix I to the right with respect to a modulo Ns by c, the 2-point is located in an (i+b−c)th row of the partial matrix Pc. In addition, an element having a value of 1 in a partial matrix Pd, located in the same row as the 2-point, will be referred to as a “3-point.” The 3-point is located in an (i+b−c+d)th column of the partial matrix Pd. An element having a value of 1 in the partial matrix Pa, located in the same column as the 3-point, will be referred to as a “4-point.” The 4-point is located in an (i+b−c+d−a)th row of the partial matrix Pa.
In the cycle structure of the LDPC code illustrated in FIG. 6, if a cycle with a length of 4 exists, the 0-point and the 4-point are located in the same position. That is, a relation between the 0-point and the 4-point is defined by Equation (2).i≡i+b−c+d−a(modNs) or i+a≡i+b−c+d(modNs)  (2)
Equation (2) can be rewritten as shown in Equation (3).a+c≡b+d(modNs)  (3)
As a result, when the relationship of Equation (3) is satisfied, a cycle with a length 4 is generated. Generally, when a 0-point and a 4p-point are identical to each other, a relation of i≅i+p(b−c+d−e)(mod Ns) is given, and the following relation shown in Equation (4) is satisfied.p(a−b+c−d)≡0(modNs)  (4)
That is, if a positive integer having a minimum value among the positive integers satisfying Equation (4) for a given a, b, c, and d is defined as ‘p’, a cycle with a length of 4p becomes a cycle having a minimum length in the cycle structure of the block LDPC code illustrated in FIG. 6.
As described above, for (a−b+c−d)≠0, if gcd(Ns, a−b+c−d)=1 is satisfied, then p=Ns. Therefore, a cycle with a length of 4Ns becomes a cycle with a minimum length.
A Richardson-Urbanke technique will be used as a coding technique for the block LDPC code. Because the Richardson-Urbanke technique is used as a coding technique, coding complexity can be minimized as the form of a parity check matrix becomes similar to the form of a full lower triangular matrix.
FIG. 7 is a diagram illustrating a parity check matrix having a form similar to that of the full lower triangular matrix. However, the parity check matrix illustrated in FIG. 7 is different from the parity check matrix having a form of the full lower triangular matrix in the form of the parity part.
In FIG. 7, a superscript (or exponent) apq of the permutation matrix P of an information part is either 0≦apq≦Ns−1 or apq=∞, as described above. A permutation matrix P with a superscript apq=0, i.e. a permutation matrix P0, of the information part represents an identity matrix INs×Ns, and a permutation matrix P with a superscript apq=∞, i.e. a permutation matrix P∞, represents a zero matrix. In addition, ‘p’ represents the number of rows of partial blocks mapped to the information part in the parity check matrix, and ‘q’ represents the number of columns of partial blocks mapped to the information part. Also, superscripts ap, x and y of the permutation matrices P mapped to the parity part represent exponents of the permutation matrix P.
However, for convenience, the different superscripts ap, x, and y are used to distinguish the parity part from the information part. That is, in FIG. 7, Pa1 to Pap are also permutation matrices, and the superscripts a1 to ap are sequentially indexed to partial matrices located in a diagonal part of the parity part. In addition, Px and Py are also permutation matrices, and for convenience, they are indexed in a different way to distinguish the parity part from the information part.
If a block size of a block LDPC code having the parity check matrix illustrated in FIG. 7 is assumed to be N, the coding complexity of the block LDPC code linearly increases with respect to the block size N (O(N)).
The biggest problem of the LDPC code having the parity check matrix of FIG. 7 is that if a size of a partial block is defined as Ns, Ns check nodes whose degrees are always 1 in a factor graph of the block LDPC code are generated. The check nodes with a degree of 1 cannot affect the performance improvement based on the iterative decoding. Therefore, a standard irregular LDPC code based on the Richardson-Urbanke technique does not include a check node with a degree of 1. Therefore, a parity check matrix of FIG. 7 will be assumed as a basic parity check matrix in order to design a parity check matrix such that it enables efficient coding while not including a check node with a degree of 1.
In the parity check matrix of FIG. 7 having the partial matrices, the selection of a partial matrix is a very important factor for a performance improvement of the block LDPC code, such that finding an appropriate selection criterion for the partial matrix also becomes a very important factor.
In order to facilitate a method of designing a parity check matrix of the block LDPC code and a method for coding the block LDPC code, the parity check matrix illustrated in FIG. 7 is assumed to be formed with six partial matrices as illustrated in FIG. 8.
FIG. 8 is a diagram illustrating the parity check matrix of FIG. 7, which is divided into six partial blocks. Referring to FIG. 8, a parity check matrix of the block LDPC code illustrated in FIG. 7 is divided into an information part ‘s’, a first parity part p1, and a second parity part p2. The information part ‘s’ represents a part of the parity check matrix, mapped to an actual information word during the process of coding a block LDPC code, like the information part described in conjunction with FIG. 7, and for convenience, the information part ‘s’ is represented by different reference letters. The first parity part p1 and the second parity part p2 represent a part of the parity check matrix, mapped to an actual parity during the process of coding the block LDPC code, like the parity part described in conjunction with FIG. 7, and the parity part is divided into two parts.
Partial matrices A and C correspond to partial blocks A (802) and C (804) of the information part ‘s’, partial matrices B and D correspond to partial blocks B (806) and D (808) of the first parity part p1, and partial matrices T and E correspond to partial blocks T (810) and E (812) of the second parity part p2. Although the parity check matrix is divided into seven partial blocks in FIG. 8, it should be noted that because ‘0’ is not a separate partial block and the partial matrix T corresponding to the partial block T (810) have a full lower triangular form, a region where zero matrices are arranged on the basis of a diagonal is represented by ‘0’. A process of simplifying a coding method using the partial matrices of the information part ‘s’, the first parity part p1, and the second parity part p2 will be described later with reference to FIG. 10.
FIG. 9 is a diagram illustrating a transpose matrix of the partial matrix B illustrated in FIG. 8, the partial matrix E, the partial matrix T, and an inverse matrix of the partial matrix T, in the parity check matrix of FIG. 7. Referring to FIG. 9, a partial matrix BT represents a transpose matrix of the partial matrix B, and a partial matrix T−1 represents an inverse matrix of the partial matrix T. The p(k1˜k2) represents
            ∏              i        =                  k          i                            k        2              ⁢                  ⁢          P              a        i              =            P                        ∑                      i            =                          k              i                                            k            2                          ⁢                                  ⁢                  a          i                      .  
The permutation matrices illustrated in FIG. 9, for example, Pa1, may be identity matrices. As described above, if an exponent of the permutation matrix, i.e., a1, is 0, the permutation matrix Pa1 will be an identity matrix. Also, if an exponent of the permutation matrix, i.e., a1, increases by a predetermined value, the permutation matrix is cyclic shifted by the predetermined value, so the permutation matrix Pa1 will be an identity matrix.
FIG. 10 is a flowchart illustrating a procedure for generating a parity check matrix of a conventional block LDPC code. However, before a description of FIG. 10 is given, it should be noted that in order to generate a block LDPC code, a codeword size and a coding rate of a block LDPC code to be generated must be determined, and a size of a parity check matrix must be determined according to the determined codeword size and coding rate. If a codeword size of the block LDPC code is represented by N and a coding rate is represented by R, a size of a parity check matrix becomes N(1−R)×N. Actually, the procedure for generating a parity check matrix of a block LDPC code illustrated in FIG. 10 is performed only once, because the parity check matrix is initially generated to be suitable for a situation of a communication system and thereafter, the generated parity check matrix is used.
Referring to FIG. 10, in step 1011, a controller divides a parity check matrix with the size N(1−R)×N into a total of p×q blocks, including p blocks in a horizontal axis and q blocks in a vertical axis. Because each of the blocks has a size of Ns×Ns, the parity check matrix includes Ns×p rows and Ns×q columns. In step 1013, the controller classifies the p×q blocks divided from the parity check matrix into an information part ‘s’, a first parity part p1, and a second parity part p2.
In step 1015, the controller separates the information part ‘s’ into non-zero blocks or non-zero matrices, and zero blocks or zero matrices, according to degree distribution for guaranteeing good performance of the block LDPC code. Because the degree distribution for guaranteeing good performance of the block LDPC code has been described above, a detailed description thereof will omitted herein.
In step 1017, the controller determines the permutation matrices Papq such that a minimum cycle length of a block cycle should be maximized in the non-zero matrix portions in blocks having a low degree from among the blocks determined according to the degree distribution for guaranteeing a good performance of the block LDPC code. The permutation matrices Papq should be determined taking into consideration the block cycles of the information part ‘s’, the first parity part p1, and the second parity part p2.
In step 1019, the controller randomly determines the permutation matrices Papq in the non-zero matrix portions in the blocks having a high degree among the blocks determined according to the degree distribution for guaranteeing a good performance of the block LDPC code, and then ends the procedure. Even when the permutation matrices Papq to be applied to the non-zero matrix portions in the blocks having a high degree are determined, the permutation matrices Papq must be determined such that a minimum cycle length of a block cycle is maximized, and the permutation matrices Papq are determined considering the block cycles of not only the information part ‘s’ but also the first parity part p1 and the second parity part p2. An example of the permutation matrices Papq arranged in the information part ‘s’ of the parity check matrix is illustrated in FIG. 9.
In step 1021, the controller divides the first part p1 and the second parity part p2 into four partial matrices B, T, D, and E. In step 1023, the controller inputs the non-zero permutation matrices Py and Pa1 to four partial blocks among the partial blocks included in the partial matrix B. The structure for inputting the non-zero permutation matrices Py and Pa1 to two partial blocks among the partial blocks included in the partial matrix B has been described with reference to FIG. 9.
In step 1025, the controller inputs the identity matrix I to the diagonal partial blocks of the partial matrix T, and inputs the particular permutation matrices Pa2, Pa3, . . . , Pam−1 to (i, i+1)th partial blocks under the diagonal components of the partial matrix T. The structure for inputting the identity matrix I to the diagonal partial blocks of the partial matrix T and inputting the particular permutation matrices Pa2, Pa3, . . . , Pam−1 to (i, i+1)th partial blocks under the diagonal components of the partial matrix T has been described with reference to FIG. 9.
In step 1027, the controller inputs a permutation matrix Px to the partial matrix D. In step 1029, the controller inputs a permutation matrix Pam to only the last partial block in the partial matrix E, and then ends the procedure. As described above, the structure for inputting the two permutation matrices Pam to only the last partial block among the partial blocks included in the partial matrix E has been described with reference to FIG. 9.
Accordingly, it is known that the LDPC code, together with the turbo code, has a high performance gain during high-speed data transmission and effectively corrects an error caused by noises generated in a transmission channel, contributing to an increase in reliability of data transmission. However, the LDPC code is disadvantageous in the coding rate. That is, because the LDPC code has a relatively high coding rate, it has a limitation in terms of the coding rate.
More specifically, among the currently available LDPC codes, major LDPC codes have a coding rate of 1/2 and only minor LDPC codes have a coding rate of 1/3 . The limitation in the coding rate exerts a fatal influence on high-speed, high-capacity data transmission. Although a degree distribution representing the best performance can be calculated using a density evolution scheme in order to implement a relatively low coding rate for the LDPC code, it is difficult to implement an LDPC code having a degree distribution exhibiting the best performance due to various restrictions, such as a cycle structure in a factor graph and hardware implementation.